1. Field of the Invention
This invention relates to an encoding device and method, a decoding device and method, and providing medium, and in particular, to an encoding device and method, a decoding device and method, and a providing medium which can conveniently be applied when performing turbo encoding or decoding.
2. Description of the Related Art
One type of code having a performance near the Shannon limit which is the theoretical limit of coding performance is a turbo code. This turbo code encodes by a structure which combines plural convolution encoding circuits and interleavers (interleaving circuits), and on the decoding side, information about input data is exchanged between decoding circuits which output plural soft outputs so as to obtain a final decoding result.
FIG. 9 shows the structure of a conventional turbo encoding device 10. This turbo encoding device 10 comprises a convolution encoding circuit 1-1 which performs convolution encoding on input data to obtain encoded data, interleavers 2-1 to 2-(Nxe2x88x921) which perform sequential interleaving on this input data (hereafter, these will be referred to simply as the interleavers 2 when it is unnecessary to distinguish the interleavers 2-1 to 2-(Nxe2x88x921) separately, the same practice being adopted for other devices), and convolution encoding circuits 1-2 to 1-N which perform convolution encoding on the outputs of these interleavers 2 to obtain encoded data.
Herein, the convolution encoding circuit 1 performs a convolution computation on the input data, and the computation results are output as encoded data.
One advantage of convolution encoding is that soft determination decoding can be performed more simply than block decoding. The interleavers 2 involute the sequence of input data to generate an output. By rearranging a pattern which gives a low output weighting with one convolution code, the interleavers 2 can increase output with other convolution codes, and can construct a high performance code by increasing the minimum distance of code words.
FIG. 10 shows one example of the convolution encoding circuit 1. The convolution encoding circuit 1 shown in FIG. 10 is a feedback type convolution encoding circuit having a restriction length 3.
This convolution encoding circuit comprises a termination circuit 21, three exclusive xe2x80x9corxe2x80x9d circuits (hereafter, xe2x80x9cEXOR circuitsxe2x80x9d) 22-1 to 22-3, and two shift registers 23-1 and 23-2, and generates encoded data from input data.
Herein, the shift registers 23 function as a delay element which delays input data by one unit time, and the EXOR circuit 22 outputs the exclusive or of the input data. Input data is output until the termination circuit 21 has finished encoding all the input data, and feedback data is output for two unit times (times corresponding to the number of shift registers) from when encoding has finished. The processing subsequent to encoding of all input data is intended to restore all the contents of the shift registers to 0, which is referred to as xe2x80x9cterminationxe2x80x9d, and decoding is performed on the decoding side assuming this processing has been performed.
The state transition diagram of the convolution encoding circuit 1 shown in FIG. 10 is as shown in FIG. 18. As shown in this diagram, the convolution encoding circuit 1 has an initial state S0, and three other states S1, S2 and S3. As shown in the diagram, when a xe2x80x9c0xe2x80x9d bit is input in the state S0, the state returns to the current state S0, and the value xe2x80x9c0xe2x80x9d is output, whereas when a xe2x80x9c1xe2x80x9d is input, a transition to the state S1 occurs and the value xe2x80x9c1xe2x80x9d is output. When a xe2x80x9c0xe2x80x9d bit is input in the state S2, a transition to the state S3 occurs and xe2x80x9c1xe2x80x9d is output, whereas when a xe2x80x9c1xe2x80x9d is input, a transition to the state S2 occurs and the value xe2x80x9c0xe2x80x9d is output. When a xe2x80x9c0xe2x80x9d bit is input in the state S2, a transition to the state S1 occurs and the value xe2x80x9c0xe2x80x9d is output, whereas when a xe2x80x9c1xe2x80x9d is input, a transition to the state S0 occurs and the value xe2x80x9c1xe2x80x9d is output. When a xe2x80x9c0xe2x80x9d bit is input in the state S3, a transition to the state S2 occurs and the value xe2x80x9c1xe2x80x9d is output, whereas when a xe2x80x9c1xe2x80x9d is input, a transition to the state S3 occurs and the value xe2x80x9c0xe2x80x9d is output.
The output of the convolution encoding circuit 1 relative to input data can be easily understood by referring to this state transition diagram.
In the convolution encoding circuit 1 shown in FIG. 18, if zero is input three times in succession, the state returns to the original state prior to input of zero. This is true even in any of the states S1, S2, S3 which are different from the initial state S0 (for example, if zero is input three times in succession in the state S1, the transition S1xe2x86x92S2xe2x86x92S3xe2x86x92S1 occurs and the state returns to the state S1). Therefore, the period p of this convolution encoding circuit 1 is 3.
FIG. 11 shows an example of the interleavers 2. Input data input to the interleavers 2 is first stored in an input data storage memory 31, and its sequence is then rearranged by a data substitution circuit 32. The rearrangement of the data sequence is performed based on the contents (substitution position information) of a substitution data ROM (Read Only Memory) 34. The data with a rearranged sequence are stored in an output storage memory 33, and then output as output data.
FIG. 11 shows a typical case of operation wherein the size of the interleavers 2 is 5, and the contents of the substitution data ROM 34 are as shown in FIG. 12. Specifically, when the input data are xe2x80x9c11010xe2x80x9d, xe2x80x9c00111xe2x80x9d is output as output data due to the data substitution circuit 32 performing substitution processing on the input data according to the data stored in the substitution data ROM 34.
The operation of the turbo encoding device 10 shown in FIG. 9 will now be described. Input data is supplied to the convolution encoding circuit 1-1. In this convolution encoding circuit 1-1, a convolution computation is performed on the input data, termination is performed, and encoded data is output by an encoding which comprises termination.
The input data is also supplied to the series of interleavers 2-1 to 2-(Nxe2x88x921), and after the sequence of the sequentially input data is involuted, the data is output. The data output by these interleavers 2-1 to 2-(Nxe2x88x921) is supplied to corresponding convolution encoding circuits 1-2 to 1-N. In these convolution encoding circuits 1-2 to 1-N, a convolution computation is performed on the output data from the corresponding interleavers 2-1 to 2-(Nxe2x88x921), termination is performed, and encoded data is output by an encoding which comprises termination.
FIG. 13 shows the relation of the data input to the turbo encoding device 10, and the number of bits of encoded data. k bits of input data are converted to an n1 bit code by the convolution encoding circuit 1-1 and a t1 bit termination is added, so the result is a (n1+t1) bit code. Similarly, (n2+t2) to (nN+tN) bits of coded data are output from the convolution encoding circuits 1-2 to 1-N.
FIG. 14 shows the construction of a prior art turbo decoding device 40. This turbo decoding device 40 comprises plural soft output decoding circuits 51-1 to 51-N corresponding to the number of encoded data (received data) output by the turbo encoding device 10. The soft output decoding circuits 51-1 to 51-N use a xe2x80x9csoft output decoding schemexe2x80x9d having the function of a MAP (Maximum A Posteriori Probability) decoder or SOVA (Soft Output Viterbi Algorithm) decoder which compute the probability of the input data being 0 or 1 on the encoding side. Soft output is a scheme wherein reliability information about a decoding result is attached to the decoding result.
The operation of the turbo decoding device 40 shown in FIG. 14 will now be described. The received data (encoded data) is supplied to the soft output decoding circuits 51-1 to 51-N. In the decoding circuits 51-1 to 51-N, repetitive decoding operations are respectively performed several times and several tens of times, making common use of estimated probability value data, on the input data excluding the termination bit on the encoding side. The final decoded data is output from any of the decoding circuits (the decoding circuit 51-1 in FIG. 51-1).
FIG. 15 shows the relation between the data received from the turbo decoding device 40, estimated probability value data and number of bits of decoded data, and it corresponds to the relation between numbers of bits in the turbo encoding device 10 of FIG. 9. The soft output decoding circuits 51-1 to 51-N respectively compute k-bits of estimated probability value data of the input data excluding the termination bit from the (n1+t1)th to the (nN+tN) th of received data. This k bits of probability value data is exchanged between decoding circuits, and k bits of decoded data are finally output.
FIG. 16 is a diagram which describes the encoded data output when a specific numeric value is input into the turbo encoding device 10. In the turbo encoding device 10 shown in FIG. 16, the input data are output as encoded data without transiting the convolution encoding circuit 1-1, and is also input to the convolution encoding circuit 1-2 and interleaver 2-1. The data input to the interleaver 2-1 are mixed up, and are output to the convolution encoding circuit 2-3.
The case will be described where, for example, xe2x80x9c0010010 . . . 0xe2x80x9d are input as input data. The relation of input data positions and substitution data positions stored in the substitution data ROM 34 of the interleaver 2-1 is shown below.
Herein, when the data xe2x80x9c0010010 . . . 0xe2x80x9d are input as shown in FIG. 16, even if the pattern xe2x80x9c1001xe2x80x9d of this data is mixed up by the interleaver 2-1, it is again substituted by xe2x80x9c1001xe2x80x9d, so when the second xe2x80x9c1xe2x80x9d is input to the convolution encoder 1-2 and convolution encoder 1-3, the entire contents of the shift registers contained therein are set to 0. Therefore, after the second xe2x80x9c1xe2x80x9d is input, 0 is output continuously. The setting of the contents of the shift registers to 0 depends on the fact that the distance between the first and second xe2x80x9c1xe2x80x9d (=3) is equal to the period p(=3, FIG. 18) of the convolution encoding circuit 1.
The interleaver 2-1 may be what is known as an xe2x80x9caffine interleaverxe2x80x9d. This is an interleaver which interleaves an ith position input signal in a position axi+b modN using the interleaver size N, a coprimal, predetermined constant a and an arbitrary constant b, according to the position i of the input signal.
Wen N=2 mxcx9c2 and a=2 m+xe2x88x921, the affine interleaver necessarily sets the sum of the distances between two arbitrary points before and after substitution as 2 m or greater. If an affine interleaver is used as the interleaver 2-1 of the turbo encoding device 10 shown in FIG. 17, and these parameters are N=32, a=7, b=0, the substitution data positions shown below are stored as the contents of the substitution data ROM 34 of the interleaver 2-1 .
The interleaver 2-1 which stores the above-mentioned substitution data positions as the contents of the substitution data ROM 34 ensures that the sum of the distances between two arbitrary points before and after substitution is 8 or greater. This property prevents replacing xe2x80x9c1001xe2x80x9d (the distance between xe2x80x9c1xe2x80x9d and xe2x80x9c1xe2x80x9d is the same 3 as the period of the convolution encoding circuit 1) by xe2x80x9c1001xe2x80x9d (the distance between xe2x80x9c1xe2x80x9d and xe2x80x9c1xe2x80x9d is the same 3 as the period of the convolution encoding circuit 1). However, when two xe2x80x9c1001xe2x80x9d are input as shown in FIG. 17, it is again substituted by the pattern xe2x80x9c1001xe2x80x9d, and a code with a small weighting of 20 is output as a result.
However, in order to obtain a high error correction performance in a turbo encoding device or a turbo decoding device, the minimum distance of the code must be increased, and an interleaver must be constructed to perform substitutions wherein the number of xe2x80x9c1xe2x80x9ds which are output (output code word weighting) is increased whatever the input may be.
However, in the interleaver 2-1 mentioned above, as only some of the patterns giving a small output code word weighting are removed, a turbo encoding device or turbo decoding device providing the desired high error correction performance could not be constructed.
This invention, which was conceived in view of the above problems, therefore aims to perform interleaving by removing patterns giving a small output code word weighting.
An interleaving means defined in claim 1 interleaves input data using an interleaving pattern from which predetermined patterns have been removed.
Specifically, removed patterns means patterns giving a small output code word weighting. For example, a pattern satisfying at least one of the first to eighth sets of relations of claim 3 to claim 10 is an interleaving pattern which makes the weighting of output code words small. By removing these patterns, a turbo encoding device and turbo decoding device which offer higher error correction performance can be constructed.
In an encoding device defined in claim 11, an interleaving means increases minimum values of code words as much as possible by removing patterns giving a small output code word weighting due to the effect of the termination bit added to the end of the interleave. Moreover, the encoding devices defined in claims 12 to 26 suppress occurrence of specific substitution patterns in the vicinity of the end of an interleaving pattern, and more specifically apply a ninth to twenty-third set of relations for detecting such substitution patterns. As a result, patterns giving a small output code word weighting due to the effect of the termination bit added to the end of the encoded data are removed, and error correction performance can be further improved.
In an encoding method defined in claim 29, an interleaving means interleaves input data using an interleaving pattern from which predetermined patterns giving a small output code word weighting are removed. The interleaving means may remove interleaving patterns for which at least one of the first to twenty-third sets of relations respectively defined in claims 3 to 10 and claims 12 to 26 holds.
A providing medium provides a program which a computer can read which causes an interleaving means to perform processing comprising a step which detects whether or not a predetermined pattern giving a small code word weighting is generated, and a re-interleaving step which re-interleaves the predetermined interleaving pattern detected by the detection step. The interleaving means may remove interleaving patterns for which at least one of the first to twenty-third sets of relations respectively defined in claims 3 to 10 and claims 12 to 26 holds.
A decoding device defined in claim 30 comprises an interleaving means which performs reverse processing to the interleave processing performed by the encoding device.
A decoding method defined in claim 31 comprises an interleaving step which performs reverse processing to the interleave processing performed by the encoding device.
A providing medium defined in claim 32 provides a program which a computer can read, which performs processing comprising a deinterleaving step which performs reverse processing to the interleave processing performed by the encoding device.
A method for generating data substitution position information comprises a first step which provisionally generates data substitution position information, a second step which determines whether or not the data substitution position information generated in the first step generates a predetermined interleaving pattern, and a third step which provisionally regenerates the substitution data position information in response to the determining result of the second step, the determination of the second step being performed according to whether at least one of the first to twenty-third sets of relations respectively defined in claims 3 to 10 and claims 12 to 26 holds. The first to eighth sets of relations hold for substitution patterns giving a small output code word weighting. The ninth to twenty-third sets of relations hold for patterns giving a small output code word weighting due to the effect of the termination bit added to the end of the encoded data.
A providing medium is a providing medium which physically provides a computer program which performs processing, on a computer system, to generate data substitution position information for performing interleaving which mixes up input data in turbo encoding. This computer program comprises a first step which provisionally generates data substitution position information, a second step which determines whether or not the data substitution position information generated in the first step generates a predetermined interleaving pattern, and a third step which provisionally regenerates the data substitution position information in response to the determining result of the second step, the determination of the second step being performed according to whether or not at least one of the first to twenty-third sets of relations respectively defined in claims 3 to 10 and claims 12 to 26 holds.
In the encoding device defined in claim 1, interleaving and encoding of input data are performed by removing substitution patterns giving a small output code word weighting, so a turbo encoding device and turbo decoding device which offer a higher error correction performance can be constructed.
In the encoding method defined in claim 29 and the providing medium, input data is interleaved using an interleaving pattern from which predetermined patterns giving a small code word weighting are removed.
In the decoding device defined in claim 30, the decoding method defined in claim 31 and the providing medium defined in claim 32, processing is performed which is the reverse of the interleave processing performed by the encoding device.
In the method for generating data substitution position information, and the providing medium, interleave patterns are generated wherein substitution patterns giving a small output code word weighting, and substitution patterns giving a small output code word weighting due to the effect of the termination bit added to the end of the encoded data, are removed.
That is, higher error correction performance is provided by a turbo encoding device and turbo decoding device by constructing a turbo encoding device which mixes up input data using an interleave pattern generated in this way.